1. Field of the Invention
This invention relates to circuitry and an electrical signal processing method for performing high-speed ripple-through modulo division operations.
2. Description of Related Art
Modulo division is used in digital computing devices such as arithmetic logic units (ALU's) and as part of address generators. The purpose of modulo division is to divide two X-bit digital input signals A and B and derive a single X-bit digital output signal Q in the form: EQU (B*Q) mod2.sup.x =A (1)
where mod2.sup.x indicates a modulo operation, which by definition is equivalent to an operation of the form: EQU B*Q=A+2.sup.x n (2)
where n is a whole number.
For a modulo 32 system, which uses a 5-bit input, the corresponding equations describing the modulo relationship between A, B, and Q are: EQU (B*Q)mod32=A (3)
and EQU B*Q=A+32n (4)
where A, B, and Q are between 0 and 31.
In order to simplify the notation used herein, an equal sign with a 32 under it (=) will hereinafter specify equivalence under modulo 32, and an equal sign without any notation under it will specify regular equivalence. In addition, M(32) denotes modulo-32 arithmetic. It is to be understood, however, that modulo 32 arithmetic, in which X=5, is to be taken as an illustrative example only, and that the principles discussed herein may easily be generalized to cover the case where X is any positive integer greater than 1, although the modulo arithmetic for X less than 5 is essentially trivial.
A wide variety of modulo division circuitry is available at present, but most such circuitry is limited in the speed at which modulo numbers A and B can be processed. This limitation is related to a property of modulo division which makes it impossible, using conventional methods, to multiply A by the inverse of B in order to obtain the quotient Q of A and B. While all odd numbers in the modulo system have defined inverses, no even number in the modulo system has a defined inverse. Thus, conventional modulo division circuitry relies upon iterative "long division" techniques involving multiple shift registers to perform successive multiply and accumulate operations, each of which must be separately clocked in order to coordinate operations, greatly reducing processing speed.